package leetcode.tree;

public class morrisPos {
    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(Node left,Node right) {
            this.left = left;
            this.right = right;
        }
    }
    public static void process(Node head){
        if (head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                }
            }
            cur = cur.right;
        }
    }
    public static void printEdge(Node head){
        Node tail = reverseEdge(head); // 先逆序
        Node cur = tail; // 从尾部开始
        while (cur != null) { // 从位到头打印
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
        reverseEdge(tail); // 再反转回来
    }
    public static Node reverseEdge(Node from) { // 单链表的逆序
        Node pre = null;
        Node next = null;
        while (from != null) {
            next = from.right;
            from.right = pre;
            pre = from;
            from = next;
        }
        return pre;
    }
}
